package done.normal_001_100;

import com.study.common.TreeNode;
import org.junit.Test;

import java.util.List;

import static com.study.util.LogUtil.info;

/**
 * 95. Unique Binary Search Trees II 不同的二叉搜索树 II
 * <p>
 * 给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
 * <p>
 * 示例:
 * 输入: 3
 * 输出:
 * [
 * [1,null,3,2],
 * [3,2,null,1],
 * [3,1,null,null,2],
 * [2,1,3],
 * [1,null,2,null,3]
 * ]
 * 解释: 以上的输出对应以下 5 种不同结构的二叉搜索树：
 * <p>
 * 1         3     3      2      1
 * \       /     /      / \      \
 * 3     2     1      1   3      2
 * /     /       \                 \
 * 2     1         2                 3
 * <p>
 * 2019-04-23 8:51 AM
 **/
@SuppressWarnings("all")
public class UniqueBinarySearchTreesII {

    public List<TreeNode> generateTrees(int n) {
        // 190427 first
        return null;
    }

    @Test
    public void test() {
        List<TreeNode> list = generateTrees(3);
        for (TreeNode treeNode : list) {
            info(treeNode);
        }
    }
}
















































/*
public List<TreeNode> generateTrees(int n) {
    if(n == 0)
        return new LinkedList<TreeNode>();
    return dfs(1,n);
}

public List<TreeNode> dfs(int start,int end) {
    List<TreeNode> res = new LinkedList<TreeNode>();
    if (start > end) {
        res.add(null);
        return res;
    }

    for (int i = start;i <= end;i++) {
        List<TreeNode> subLeftTree = dfs(start, i-1);
        List<TreeNode> subRightTree = dfs(i+1, end);
        for (TreeNode left : subLeftTree) {
            for (TreeNode right : subRightTree) {
                res.add(new TreeNode(i, left, right));
            }
        }
    }
    return res;
}
*/
